<?
include_once "SortHelper/SortHelper.php";
/**
 * 归并排序
 * 关键点：每次分两段进行排序，有点像二分法。先分到底，然后归并排序
 * 待排序数组：[2,3,6,8,1,4,5,7]
 * 排序过程:（数字正下面的符号或者字母标识当前数字代表的意思）
 * 
 * 初始化原始待排数据标定点：
 * k
 * ▼
 * 2    3   6   8   1   4   5   7
 * 
 * 2    3   6   8 | 1   4   5   7
 * ▲                ▲
 * l,i          m   j           r(right)
 * 
 * 
 * 进行归并排序：
 * k左边的表示已经排好序，k右边的表示还未排序
 *                  k
 *                  ▼
 * 1    2   3   4   1   4   5   7
 * 
 * 2    3   6   8 | 1   4   5   7
 *          ▲               ▲
 * l(left)  i   m(middle)   j   r(right)
 */
function mergeSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }
    echo 'arr数组的长度：'. $arr_len."\n";
    merge_sort($arr, 0, $arr_len - 1);
}
//递归调用对arr[l...r]的范围进行排序
function merge_sort(&$arr, $l, $r)
{
    
    if ($l >= $r) {
        return;    
    }
    $mid = intval(($l + $r) / 2);
    
    merge_sort($arr, $l, $mid);
    merge_sort($arr, $mid + 1, $r);
    mergeData($arr, $l, $mid, $r);

}

function mergeData(&$arr, $l, $mid, $r){

    //将数组arr[l...mid]和arr[mid + 1...r]两部分进行合并
    /**
     * 写法1：
     */
    $temparr = [];
    $k = $l;
    $i = $l;
    $j = $mid + 1;
    while($i != $mid + 1 && $j != $r+1)
    {
        if($arr[$i] >= $arr[$j]){
            $temparr[$k++] = $arr[$j++];
        }else{
            $temparr[$k++] = $arr[$i++];
        }
    }

    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){
        $temparr[$k++] = $arr[$i++];
    }
    
    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $r+1){
        $temparr[$k++] = $arr[$j++];
    }

    for($i = $l; $i <= $r; $i++){
        $arr[$i] = $temparr[$i];
    }
}

$start = microtime(true);
$arr = [2,3,6,8,1,4,0,5,7];
mergeSort($arr);
$endtime = microtime(true);
echo '排序耗时：'.($endtime - $start) .'毫秒'."\n";
for ($i=0; $i < count($arr); $i++) { 
    echo $arr[$i].', ';
}